Couple de Bézout pour 200 et 116 - Corrigé

Énoncé

À l'aide de l'algorithme d'Euclide, déterminer le PGCD de  \(200\)  et  \(116\) , ainsi que deux entiers relatifs \(u\) et \(v\) tels que \(200u+116v=\mathrm{PGCD}(200;116)\) .

Solution

On applique l'algorithme d'Euclide pour \(200\) et \(116\) :

\(\begin{align*}\renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|c|}\hline a&b&q&r\\ \hline 200&116&1&84\\ \hline 116&84&1&32\\ \hline 84&32&2&20\\ \hline 32&20&1&12\\ \hline 20&12&1&8 \\ \hline 12&8&1&4 \\ \hline 8&4&2&0\\ \hline \end{array} \begin{array}{ll}\ & \\ \times (-11)& \text{suppression du reste } 84 \\ \times 8& \text{suppression du reste } 32 \\ \times (-3)& \text{suppression du reste } 20 \\ \times 2& \text{suppression du reste } 12\\ \times (-1)& \text{suppression du reste } 8\\ \times 1& \text{conservation du PGCD}\\ & \end{array}\end{align*}\)   

On en déduit que  \(\mathrm{PGCD}(200;116)=4\) .

En additionnant les lignes après avoir éliminé les restes intermédiaires, on obtient :
\(\begin{align*}200 \times (-11)+116 \times 8=116 \times 1 \times (-11)+4& \ \ \Longleftrightarrow \ \ 200 \times (-11)+116 \times 19=4\end{align*}\)  
donc le couple \((u;v)=(-11;19)\) convient.